package linked_list

import (
	"fmt"
)

// ListNode 链表节点
// next: 指向下一个节点的地址
// value: 当前节点的值
type ListNode struct {
	next *ListNode
	value interface{}
}

// LinkedList 单链表
type LinkedList struct {
	head *ListNode
}

// Print 输出单链表
func (ll *LinkedList) Print() {
	cur := ll.head.next
	format := ""

	for cur != nil {
		format += fmt.Sprintf("%+v", cur.value)
		cur = cur.next
		if cur != nil {
			format += "->"
		}
	}

	fmt.Println(format)
}

// Reverse 单链表反转
func (ll *LinkedList) Reverse() {
	if ll.head == nil || ll.head.next == nil || ll.head.next.next == nil {
		return
	}

	// 第一个节点
	cur := ll.head.next
	// 第一个节点的前一个，为 nil
	// 排列顺序为 pre(nil) cur(1) 2 3 4 5 nil
	var pre *ListNode = nil

	for cur != nil {
		// 记住当前节点指向的下一个节点地址
		tmp := cur.next

		// 指向前一个节点，指针属性赋值后，会发生改变
		cur.next = pre

		// 移动前一个节点为当前节点
		pre = cur

		// 下一个节点为当前节点
		cur = tmp
	}

	ll.head.next = pre
}

// HasCycle 是否有环
// slow 和 fast 同时指向链表的头节点
// slow 每次移动一个节点，fast 移动两个节点，直到两个指向的节点相同
func (ll *LinkedList) HasCycle() bool {
	if ll.head == nil {
		return false
	}

	// slow 和 fast 都指向头节点
	slow := ll.head
	fast := ll.head

	// fast 循环赋值，必须判断是否为 nil
	for fast != nil && fast.next != nil {
		slow = slow.next
		fast = fast.next.next

		if slow == fast {
			return true
		}
	}

	return false
}

// MergeSortedList 合并两个有序链表
func MergeSortedList(l1, l2 *LinkedList) *LinkedList {
	if l1 == nil || l1.head == nil || l1.head.next == nil {
		return l2
	}

	if l2 == nil || l2.head == nil || l2.head.next == nil {
		return l1
	}

	// 定义一个临时头节点
	l := &LinkedList{head: &ListNode{}}
	cur := l.head

	// 从两个链表的头节点分别设立指针
	curL1 := l1.head.next
	curL2 := l2.head.next

	for curL1 != nil && curL2 != nil {
		// 判断大小，并将较小的那个链入临时节点的末尾
		if curL1.value.(int) > curL2.value.(int) {
			cur.next = curL2
			curL2 = curL2.next
		} else {
			cur.next = curL1
			curL1 = curL1.next
		}

		// 移动指针到临时节点末尾
		cur = cur.next
	}

	// 如果有一个链表到了末尾，则直接将剩下的部分链入到临时链表
	if curL1 != nil {
		cur.next = curL1
	}

	if curL2 != nil {
		cur.next = curL2
	}

	return l
}

// DeleteBottomN 删除倒数第 n 个节点
func (ll *LinkedList) DeleteBottomN(n int) {
	if n <= 0 || ll.head == nil || ll.head.next == nil {
		return
	}

	fast := ll.head

	// 循环获取第 n 个结点
	for i := 1; i <= n && fast != nil; i++ {
		fast = fast.next
	}

	// 超过了最后一个
	if fast == nil {
		return
	}

	slow := ll.head
	for fast.next != nil {
		// 均向前移动，保持 n 个结点的距离 n = fast.value.(int) - slow.value.(int)
		slow = slow.next
		fast = fast.next
	}

	// 删除倒数第 n 个结点
	slow.next = slow.next.next
}

// FindMiddleNode 查找链表的中间节点
func (ll *LinkedList) FindMiddleNode() *ListNode {
	if ll.head == nil || ll.head.next == nil {
		return nil
	}

	// 如果只有一个结点，直接返回
	if ll.head.next.next == nil {
		return ll.head.next
	}

	slow, fast := ll.head, ll.head

	// 慢的指针每次移动一个结点，快的结点每次移动2个结点
	for fast != nil && fast.next != nil {
		slow = slow.next
		fast = fast.next.next
	}

	// 当快指针指向 nil 时，说明 slow 指针移动到了中间
	return slow
}

